<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Medium
  </div>
  <div>
   <h1 class="question_title">
    678. Valid Parenthesis String
   </h1>
   <p>
    Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:
   </p>
   <ol>
    <li>
     Any left parenthesis
     <code>
      '('
     </code>
     must have a corresponding right parenthesis
     <code>
      ')'
     </code>
     .
    </li>
    <li>
     Any right parenthesis
     <code>
      ')'
     </code>
     must have a corresponding left parenthesis
     <code>
      '('
     </code>
     .
    </li>
    <li>
     Left parenthesis
     <code>
      '('
     </code>
     must go before the corresponding right parenthesis
     <code>
      ')'
     </code>
     .
    </li>
    <li>
     <code>
      '*'
     </code>
     could be treated as a single right parenthesis
     <code>
      ')'
     </code>
     or a single left parenthesis
     <code>
      '('
     </code>
     or an empty string.
    </li>
    <li>
     An empty string is also valid.
    </li>
   </ol>
   <p>
    <b>
     Example 1:
    </b>
    <br>
   </p>
   <pre>
<b>Input:</b> "()"
<b>Output:</b> True
</pre>
   <p>
    <b>
     Example 2:
    </b>
    <br>
   </p>
   <pre>
<b>Input:</b> "(*)"
<b>Output:</b> True
</pre>
   <p>
    <b>
     Example 3:
    </b>
    <br>
   </p>
   <pre>
<b>Input:</b> "(*))"
<b>Output:</b> True
</pre>
   <p>
    <b>
     Note:
    </b>
    <br>
   </p>
   <ol>
    <li>
     The string size will be in the range [1, 100].
    </li>
   </ol>
  </div>
  <div>
   <h1 class="question_title">
    678. 有效的括号字符串
   </h1>
   <p>
    给定一个只包含三种字符的字符串：
    <code>
     （&nbsp;
    </code>
    ，
    <code>
     ）
    </code>
    &nbsp;和
    <code>
     *
    </code>
    ，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
   </p>
   <ol>
    <li>
     任何左括号
     <code>
      (
     </code>
     &nbsp;必须有相应的右括号
     <code>
      )
     </code>
     。
    </li>
    <li>
     任何右括号
     <code>
      )
     </code>
     &nbsp;必须有相应的左括号
     <code>
      (
     </code>
     &nbsp;。
    </li>
    <li>
     左括号
     <code>
      (
     </code>
     必须在对应的右括号之前
     <code>
      )
     </code>
     。
    </li>
    <li>
     <code>
      *
     </code>
     &nbsp;可以被视为单个右括号
     <code>
      )
     </code>
     &nbsp;，或单个左括号
     <code>
      (
     </code>
     &nbsp;，或一个空字符串。
    </li>
    <li>
     一个空字符串也被视为有效字符串。
    </li>
   </ol>
   <p>
    <strong>
     示例 1:
    </strong>
   </p>
   <pre>
<strong>输入:</strong> "()"
<strong>输出:</strong> True
</pre>
   <p>
    <strong>
     示例 2:
    </strong>
   </p>
   <pre>
<strong>输入:</strong> "(*)"
<strong>输出:</strong> True
</pre>
   <p>
    <strong>
     示例 3:
    </strong>
   </p>
   <pre>
<strong>输入:</strong> "(*))"
<strong>输出:</strong> True
</pre>
   <p>
    <strong>
     注意:
    </strong>
   </p>
   <ol>
    <li>
     字符串大小将在 [1，100] 范围内。
    </li>
   </ol>
  </div>
 </body>
</html>